This invention generally relates to a system and method for resource optimization, and more particularly to a system and method for problem modeling in resource optimization.
Generally, the amount of profit that a company earns is directly related to how efficiently the company can utilize its costly or limited resources. The optimal allocation of resources is therefore a critical function in many areas of business for both the service and manufacturing industries. Optimal allocation of resources can, for example, lower costs, reduce waste, shorten cycle time, improve throughput or response time, accelerate delivery time, and optimize equipment design. Some business allocation problems are simple enough to be solved with a direct solution. For many other resource allocation problems, however, the problem structure is complex or the number of possible solutions is extremely large. Optimization techniques have been developed for these situations to determine the optimal solution from a set of possible solutions.
There are many business domains in which optimization techniques provide significant improvement in resource allocation. Optimization can benefit business situations which involve, for example, costly assets, high sensitivity to tradeoffs among decision factors, or narrow margins for error. Specifically, applications for optimization include telecommunications network optimization, supply chain optimization, logistics resource allocation in airports and ports, manpower scheduling, maintenance scheduling, production planning, vehicle dispatching, and technician dispatching.
There are a variety of optimization techniques available, and the specific type used generally depends on the structure of the problem. Typically, if all variables are real, and all functions are linear, then linear programming is appropriate. If a problem includes integer variables, then integer programming may be used. Other techniques include the use of genetic algorithms to control evolution of the population of solutions, and the use of simulated annealing to control the rate movement in the solution space. The technique of domain reduction and constraint propagation is useful for problems with a wide variety of variables and constraints, such as integer, logical and choice variables, and linear and logical constraints. Each of these techniques is described more fully in xe2x80x9cOptimization Technology White Paper,xe2x80x9d ILOG, Inc., 1997.
Generally, optimization involves two phases: first modeling the problem and then solving the problem. Modeling of the problem is typically performed by an application developer while designing software for a particular user application. Solving of the problem is then typically performed by a solver program at the request of the user application.
In the prior art, an application developer familiar with operations research algorithms generally models a problem manually. The developer typically speaks with a domain expert familiar with the particular industrial application or problem. The expert communicates the problem to be solved in descriptive terms to the developer, who then interprets the information and transforms it into a mathematical model consisting of objective and/or cost functions, and constraints, which abstractly represent the problem. These are often represented as mathematical matrices for traditional linear/integer programming algorithms. The terms xe2x80x9cobjectivexe2x80x9d and xe2x80x9ccost,xe2x80x9d when used in reference to functions, are used interchangeably herein. The developer typically writes software code containing the mathematical model in an object oriented software language such as C++ by calling functions stored in C++ class libraries supplied with a vendor""s optimization software suite.
This method of implementation effectively creates a hard-coded mathematical model of the problem for a specific application. This occurs, for example, because simplifying assumptions are generally made about the problem which are very specific to a given application. The result is then a specialized optimization model for a specific application in a specific domain, such as a specific video conferencing network scheduler system for a particular customer. The application developer inputs the information into a fixed data source, from which a user application may extract data and transform it into parameters that are transferred to the solver program. Generally, the data extracted from the data source is transformed using hard-coded functions generated in the implementation phase by the application developer. The parameters are provided to the problem solver in a very specific format so that the problem solver can process them. The developer may also write an application programming interface (API) to handle the interface between the solver program and the application program.
During operation, the user application program sends a solution request to the solver program. The solver program calculates an optimal solution for the solution request by applying an optimization technique to the solution request, subject to the parameters provided by the user application, and then returns an optimized solution result to the application program.
Prior art optimization software suites may contain a solver program which can receive a solution request from a user application via an API, interpret parameters representing the characteristics of the problem and transferred in a specific format from the user application, calculate an optimized solution, and return the optimized solution to the user application via the API. The prior art optimization software suites, however, still require that an application developer manually hard-code functions for the transformation of the data from the data source into the properly formatted parameters to be interpreted by the problem solver.
Accordingly, it is an object of the present invention to generally provide a generic problem modeler which can examine an existing user information resource and transform the relevant information from the resource into data that can be stored in a solver database which is directly accessible by a problem solver.
It is another object of the invention to provide a generic problem modeler which generally requires substantially less user skill than prior art systems and methods for creating models for resource optimization problems.
These and other objects, features and technical advantages generally are achieved by a system and method which examine a user information resource and transform data objects and object relationships from the resource into optimization metrics for storage in a problem solver database. A preferred embodiment resource optimization system in accordance with the present invention comprises a problem modeler having an interface for retrieving user data objects and object relationships describing a user application from a user information resource, a solver database to which the problem modeler has an interface for storing optimization metrics derived from the user data objects and object relationships by the problem modeler, and a problem solver having an interface to the solver database for retrieving the optimization metrics for solving resource optimization problems for the user application.
A preferred embodiment method for robotically modeling a user application optimization problem in accordance with the present invention comprises examining a user information resource for database objects and object relationships relevant to solving the optimization problem, transforming the database objects and object relationships into optimization metrics readable by a solver program, and storing the optimization metrics in a solver database accessible by the solver program. A preferred embodiment method for robotically solving a user application optimization problem additionally comprises receiving a solution request to the optimization problem from the user application, retrieving the optimization metrics from the solver database, calculating an optimized solution for the solution request subject to the optimization metrics, and sending the optimized solution to the user application.
A preferred embodiment computer program product for modeling a user application optimization problem in accordance with the present invention comprises a computer readable medium and a computer program stored on the computer-readable storage medium. The computer program comprises means for examining a user information resource for database objects and object relationships relevant to solving said optimization problem, means for transforming the database objects and the object relationships into optimization metrics readable by a solver program, and means for storing the optimization metrics in a solver database accessible by the solver program.
According to yet another preferred embodiment, the optimization metrics stored in the solver database are updated in real-time in response to changes in the data objects and the object relationships in the user information resource.
An advantage of the present invention is that it generally provides a generic problem modeler which can examine an existing user information resource and transform the relevant information from the resource into data that can be stored in a solver database which is directly accessible by a problem solver.
It is another advantage of the invention that it provides a generic problem modeler which generally requires substantially less user skill than prior art systems and methods for creating models for resource optimization problems.
The foregoing has outlined rather broadly the features and technical advantages of the present invention in order that the detailed description of the invention that follows may be better understood. Additional features and advantages of the invention will be described hereinafter which form the subject of the claims of the invention. It should be appreciated by those skilled in the art that the conception and specific embodiment disclosed may be readily utilized as a basis for modifying or designing other structures for carrying out the same purposes of the present invention. It should also be realized by those skilled in the art that such equivalent constructions do not depart from the spirit and scope of the invention as set forth in the appended claims.